package interview.longestcommonsubstring;

import java.util.HashSet;

public class LongestCommonSubstring {
	public HashSet<String> run(String source, String substr) {
		HashSet<String> result = new HashSet<String>();
		
		int[][] DPTable = new int[source.length() + 1][substr.length() + 1];
		for(int i = 0; i < substr.length() + 1; i++) {
			DPTable[0][i] = 0;
		}
		for(int i = 0; i < source.length() + 1; i++) {
			DPTable[i][0] = 0;
		}
		
		int maxLen = 0;
		for(int i = 1; i < substr.length() + 1; i++) {
			for(int j = 1; j < substr.length() + 1; j++) {
				if(substr.charAt(i - 1) == source.charAt(j - 1)) {
					DPTable[i][j] = DPTable[i - 1][j - 1] + 1;
					if(DPTable[i][j] > maxLen) {
						maxLen = DPTable[i][j];
						result.clear();
					}
					if(DPTable[i][j] == maxLen) {
						result.add(substr.substring(i - maxLen, i));
					}
				} else {
					DPTable[i][j] = 0;
				}
			}
		}
		
		return result;
	}
}
